#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode() {
	this->dest = 0;
	this->link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link) {
	this->dest = dest;
	this->link = link;
}

EdgeNode::~EdgeNode() {

}

int EdgeNode::getDest() {
	return this->dest;
}

EdgeNode* EdgeNode::getNext() {
	return this->link;
}

void EdgeNode::setDest(int dest) {
	this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link) {
	this->link = link;
}

VertexNode::VertexNode() {
	this->data = '\0';
	this->firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge) {
	this->data = data;
	this->firstEdge = firstEdge;
}

VertexNode::~VertexNode() {

}

char VertexNode::getData() {
	return this->data;
}

EdgeNode* VertexNode::getFirstEdge() {
	return this->firstEdge;
}

void VertexNode::setData(char data) {
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge) {
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph() {
	this->nodeNum = 0;
	this->edgeNum = 0;
	this->VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) {
	this->nodeNum = nodeNum;
	this->edgeNum = edgeNum;
	this->VexList = new VertexNode[this->nodeNum];
	for (int i = 0; i < this->nodeNum; i++)
		this->VexList[i].setData(nodeList[i]);
	for (int i = 0; i < this->edgeNum; i++) {
		int start = edgeStartList[i];
		int end = edgeEndList[i];
		EdgeNode* edge = new EdgeNode(end, this->VexList[start].getFirstEdge());
		this->VexList[start].setFirstEdge(edge);
		EdgeNode* edge1 = new EdgeNode(start, this->VexList[end].getFirstEdge());
		this->VexList[end].setFirstEdge(edge1);
	}
}

MyGraph::~MyGraph() {

}

int MyGraph::getNodeNum() {
	return this->nodeNum;
}

int MyGraph::getEdgeNum() {
	return this->edgeNum;
}

string MyGraph::printGraph() {
	string result = "";
	for (int i = 0; i < this->nodeNum; i++) {
		result += (this->VexList[i].getData());
		result += ":";
		EdgeNode* edge = this->VexList[i].getFirstEdge();
		while (edge != NULL) {
			result += " ";
			result += (this->VexList[edge->getDest()].getData());
			edge = edge->getNext();
		}
		if (i != this->nodeNum - 1) {
			result += "\n";
		}
	}
	return result;
}

int MyGraph::getFirstNeighbor(int v, int* visited) {
	return 0;
}

int MyGraph::getNextNeighbor(int v, int w, int* visited) {
	return 0;
}

void MyGraph::DFS(int v, int* visited, string& result) {
	visited[v] = 1;
	EdgeNode* edge;
	result += this->VexList[v].getData();
	result += " ";
	edge = this->VexList[v].getFirstEdge();
	while (edge != NULL) {
		if (visited[edge->getDest()] == 0) {
			DFS(edge->getDest(), visited, result);
		}
		edge = edge->getNext();
	}
}

string MyGraph::graph_DFS_Traverse() {
	int n = this->nodeNum;
	int* visited = new int[n];
	string result = "";
	for (int i = 0; i < n; i++) {
		visited[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		if (visited[i] == 0) {
			DFS(i, visited, result);
		}
	}
	delete[] visited;
	return result;
}

void MyGraph::BFS(int v, int* visited, string& result) {
	
}

string MyGraph::graph_BFS_Traverse() {
	int n = this->nodeNum;
	int* visited = new int[n];
	string result = "";
	for (int i = 0; i < n; i++) {
		visited[i] = 0;
	}
	queue<int>q;
	for (int i = 0; i < n; i++) {
		if (visited[i] == 0) {
			EdgeNode* edge;
			result += this->VexList[i].getData();
			result += " ";
			visited[i] = 1;
			q.push(i);
			while (!q.empty()) {
				int f = q.front();
				q.pop();
				edge = this->VexList[f].getFirstEdge();
				while (edge != NULL) {
					if (visited[edge->getDest()] == 0) {
						q.push(edge->getDest());
						result += this->VexList[edge->getDest()].getData();
						result += " ";
						visited[edge->getDest()] = 1;
					}
					edge = edge->getNext();
				}
			}
		}
	}
	delete[] visited;
	return result;
}